﻿//泰波那契序列 Tn 定义如下： 
//
//T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn + 3 = Tn + Tn + 1 + Tn + 2
//
//给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/n-th-tribonacci-number
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int tribonacci(int n) {
        //1.dp表
        //2.状态表示
        //3.状态转移方程
        //4. 题目要求+返回对应的状态
        if (n == 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        // int dp[n+1];  //创建dp表
        // dp[0] = 0; dp[1] = 1; dp[2] = 1; //初始化
        // //填表
        // for(int i=3; i<=n;++i)
        // {
        //     dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        // }
        //进行空间优化版本   滚动数组的方式
        int a = 0; int b = 1; int c = 1; int d = 0;
        for (int i = 3;i <= n;++i)
        {
            d = a + b + c;
            a = b; b = c; c = d;
        }
        return d;
    }
};